package newcoder_exp.justPractise;

import tree.TreeNode;

public class Ex102 {
    public class Solution {
        /**
         * 最近公共祖先（没有重复值）
         * @param root TreeNode类 
         * @param o1 int整型 
         * @param o2 int整型 
         * @return int整型
         */
        public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
            return dfs(root, o1, o2).common.val;
        }

        public Info dfs(TreeNode root, int p, int q) {
            if (root == null) return new Info(false, false, null);
            Info left = dfs(root.left, p, q), 
            right = dfs(root.right, p, q);
            if (left.common != null || right.common != null)
                 return left.common == null ? right : left;
            Info cur = new Info();

            if (left.hasP && right.hasQ || left.hasQ && right.hasP) {
                return new Info(true, true, root);
            }

            if (root.val == p) {
                if (left.hasQ || right.hasQ) {
                    cur.common = root;
                    cur.hasP = true;
                } else {
                    cur.hasP = true;
                    cur.hasQ = false;
                }
            }

            if (root.val == q) {
                if (left.hasP || right.hasP) {
                    cur.common = root;
                    cur.hasQ = true;
                } else {
                    cur.hasQ = true;
                    cur.hasP = false;
                }
            }

            if (left.hasP || right.hasP) cur.hasP = true;
            if (left.hasQ || right.hasQ) cur.hasQ = true;
            return cur;
        }
    }
    
    class Info {
        TreeNode common;
        boolean hasP, hasQ;
        public Info() {

        }
        public Info(boolean hasP, boolean hasQ, TreeNode common) {
            this.hasP = hasP;
            this.hasQ = hasQ;
            this.common = common;
        }
    }
}
